package problem_everyday;

public class D2025_07_09_P3439 {
    // 3439. 找到会议安排中的最大空闲时间
    /*
    * 允许移动会议k次，求相邻两次会议之间的最大空闲时间，跟0和eventTime之间的空闲时间也在内
    * 不允许改变会议的排列顺序
    *
    * 解决方案：滑动窗口 + 前缀和
    * */
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int res = 0;
        int[] pre_sum = new int[n+1];
        // 统计前i个会议的累积时长
        for(int i=0; i<n; i++){
            pre_sum[i+1] = pre_sum[i] + endTime[i] - startTime[i];
        }
        int left, right;

        // 先找到左右边界，然后再减去会议时长
        for(int i = k-1; i<n; i++){
            if(i==n-1){
                right = eventTime;
            } else {
                right = startTime[i+1];
            }
            if(i==k-1){
                left = 0;
            } else {
                left = endTime[i-k];
            }
            res = Math.max(res, right - left -(pre_sum[i+1] - pre_sum[i-k+1]));
        }
        return res;
    }
}
